/*
 * 1392. 打劫房屋
 * 假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。
 * 给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。
 * 
 * 
 * 样例
 * 给定 [3, 8, 4], 返回 8.
 * 
 * 挑战
 * O(n) 时间复杂度 且 O(1) 存储。
 * 
 * 2018.06.12 @jeyming
 */
package house_robber_1392;

import java.util.Arrays;

public class House_robber_1392 {
	/**
	 * @param A: An array of non-negative integers
	 * @return: The maximum amount of money you can rob tonight
	 */
	public static long houseRobber(int[] A) {
		// write your code here
		long money = 0;
		//		for(int i = 0; i < A.length; ) {
		//			if(i + 1 == A.length && money == 0) {
		//				money += A[i];
		//				break;
		//			} else {
		//				if(A[i] < A[i+1]) {
		//					money += A[i+1];
		//					i += 3;
		//				} else {
		//					money += A[i];
		//					i += 2;
		//				}
		//			}
		//		}
		int[] position = new int[A.length];
		int[] copyA = new int[A.length];
		for(int i = 0; i < A.length; ++i) {
			copyA[i] = A[i];
		}
		Arrays.sort(copyA, 0, copyA.length);
		for(int i = copyA.length - 1; i >= 0; --i) {
			for(int j = 0; j < A.length; ++j) {
				if(A[j] == copyA[i] && position[j] == 0) {
					if(A.length == 1) {
						return A[j];
					} else {
						money += A[j];
						position[j] = 1;
						if(j - 1 >= 0)
							position[j - 1] = 1;
						if(j + 1 != A.length)
							position[j + 1] = 1;
						A[j] = -1;
					}
					break;
				}
			}
		}
		return money;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		int num[] = {3,8,4};
//		int num1[] = {2};
		int num2[] = {828,125,740,724,983,321,773,678,841,842,875,377,674,144,340,467,625,916,463,922,255,662,692,123,778,766,254,559,480,483,904,60,305,966,872,935,626,691,832,998,508,657,215,162,858,179,869,674,452,158,520,138,847,452,764,995,600,568,92,496,533,404,186,345,304,420,181,73,547,281,374,376,454,438,553,929,140,298,451,674,91,531,685,862,446,262,477,573,627,624,814,103,294,388};
		//System.out.println(houseRobber(num));
		//System.out.println(houseRobber(num1));
		System.out.println(houseRobber(num2));
	}

}
